package com.leetcode.problems034;

/**
 * https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/
 * @Date 2021/11/20 14:34
 * @Author ghery
 * @Version V1.0
 */
public class Solution {


    public int[] searchRange(int[] nums, int target) {
        int l = floor(nums,target);
        if(l == -1 || nums[l] != target){
            return new int[]{-1,-1};
        }
        int r = ceil(nums,target);
        return new int[]{l,r};
    }

    /**
     * 大于等于target的第一个数的下标
     * @param nums
     * @param target
     * @return
     */
    public int ceil(int[] nums, int target){
        int l = 0;
        int r = nums.length - 1;
        int ans = nums.length;
        while(l <= r){
            int mid = l + (r - l) / 2;
            if(nums[mid] <= target){
                l = mid + 1;
            }else{
                r = mid - 1;
                ans = mid;
            }
        }
        if(ans - 1 >= 0 && nums[ans - 1] == target){
            return ans - 1;
        }
        if(ans == nums.length){
            return -1;
        }
        return ans;
    }

    /**
     * 小于等于target的第一个数的下标
     * @param nums
     * @param target
     * @return
     */
    public int floor(int[] nums, int target){
        int l = 0;
        int r = nums.length - 1;
        int ans = -1;
        while(l <= r){
            int mid = l + (r - l) / 2;
            if(nums[mid] >= target){
                r = mid - 1;
            }else{
                l = mid + 1;
                ans = mid;
            }
        }
        if(ans + 1 < nums.length && nums[ans + 1] == target){
            return ans + 1;
        }
        return ans;
    }
    public static void main(String[] args) {
        int[] nums = {1,2,3,4,5,6};
        System.out.println(new Solution().searchRange(nums,8));
    }
}
